In environments where available data storage is limited, and/or where the amount of data to be stored is large, data compression may enable a larger amount of data to be stored in a database or other data storage of finite size. Certain data compression techniques employ an external reference dictionary to hold data elements that occur frequently across multiple data records. During compression of data records, these compression techniques replace the frequent terms with a reference into the external dictionary, thus reducing the amount of space required to store the records. However, in cases where the records to be compressed include a substantial amount of infrequently occurring data, such compression techniques may be less effective.